leetcode-Longest Substring Without Repeating Characters

寻找最长无重复子串的最优解法

leetcode 原题：
Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

网上有很多不同类型的解法，这里不做一一介绍，提供一个时间复杂度O(n)，空间复杂度O(1)的解法如下：

思路：

该问题的通常解法是遍历每个字符起始的子串，找出结果。在计算过程中使用hash存储中间结果。通过遍历的方式时间复杂度为O(n^2)。
可以考虑使用DP，因为对于字符串中的一个字符而言，如果其与 其前面字符结尾的最长不重复子串 中的字符没有重复的话。那么就可以将其加入到最长不重复子串中，则以当前字符结尾的子串长度为其前面找到的子串长度+1。若有重复，如果有重复，且重复位置在上一个最长子串起始位置之后，那么就与该起始位置之后的稍短的子串构成新的子串或者单独成一个新子串。dp表中记录以每个字符结尾的最长不重复子串。
例如：有字符串abccd,有dp[0]=1,dp[1]=2,dp[2]=3。那么当找到第二个c时，此时以第一个c结尾的最长不重复子串长度为dp[2]=3（abc），发现有重复，则修改：dp[3]=1。找到d时，与前面的不重复子串没有相同字符，故dp[4]=2。
这样的dp算法的时间复杂度为O(n^2)。因为每次我们都需要“回头”去寻找重复元素的位置。
怎么样才能不回头找呢？用hash咯。可以用hash记录元素是否出现过，key为元素值，value为元素上一次出现的位置。同时可以发现，其实我们不需要维护一张DP表，因为我们只需要记住以当前元素的前一个元素结尾的最长不重复子串的长度即可。所以可以进一步优化空间使用从O(n) -> O(1)。

代码如下：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() <= 0)
            return 0;
        int maxLen = 1;
        int lastIndex = 0;
        int current = 1;
        HashMap<Character,Integer> map = new HashMap<>();
        map.put(s.charAt(0),0);
        for (int i=1; i<s.length(); i++) {
            if (map.get(s.charAt(i)) == null) {
                map.put(s.charAt(i), i);
                current++;
            } else if (lastIndex <= map.get(s.charAt(i))) {
                current = i - map.get(s.charAt(i));
                lastIndex = map.get(s.charAt(i))+1;
                map.put(s.charAt(i), i);
            } else {
                current++;
                map.put(s.charAt(i), i);
            }
            if (current > maxLen) {
                maxLen = current;
            }
        }
        return maxLen;
    }
}

参考：
http://xfhnever.com/2014/10/30/algorithm-lnrs/

leetcode-Longest Substring Without Repeating Characters

谢谢~